package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 分割等和子集
 * @author qulq
 * @date 2024-07-10 21:57:53
 */
public class T416_PartitionEqualSubsetSum{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new T416_PartitionEqualSubsetSum().new Solution();
		 System.out.println(solution.canPartition(new int[]{1, 2, 3, 5}));
	 }

	/**
	 * dp[j]：从下标[0-i]的物品里取，容量为j，最大能装多少
	 */

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canPartition(int[] nums) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if (sum % 2 == 1) {
			return false;
		}
		int target = sum / 2;
		int[] dp = new int[target + 1];
		for (int i = 0; i < nums.length; i++) {
			for (int j = target; j >= nums[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
			}
		}
		return dp[target] == target;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}